package testSort;

public class TestSort {

	public static void insertSort(int array[]) {
		int i, j, key;
		int length = array.length;
		for (i = 1; i < length; i++) {
			key = array[i];
			for (j = i - 1; j >= 0 && array[j] > key; j--) {
				array[j + 1] = array[j];
			}
			array[j + 1] = key;
		}
	}

	private static int partition(int array[], int low, int high) {
		int pivot = array[low];
		int tmp = 0;

		while (low < high) {
			while (low < high && array[high] >= pivot) {
				--high;
			}

			tmp = array[low];
			array[low] = array[high];
			array[high] = tmp;

			while (low < high && array[low] <= pivot) {
				++low;
			}

			tmp = array[low];
			array[low] = array[high];
			array[high] = tmp;
		}
		return low;
	}

	public static void quickSort(int array[], int low, int high) {
		if (low < high) {
			int n = partition(array, low, high);
			quickSort(array, low, n);
			quickSort(array, n + 1, high);
		}
	}
}
